#include<iostream>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        // 答案 = max{以heights[i]为高，左右扩展，能得到的最大面积}
        int n = heights.size();
        stack<int> st; // 单调增栈（保存索引）
        int maxArea = 0;
        int h, left, right;

        // 如果末尾不加0，当遍历完heights时，栈内可能还有值，这就代表着以栈内这些索引（的对应值）为高度的面积没有被计算。
        // 所以必须加上一个很小的数，比栈内所有值都小的即可。并不一定是0
        heights.push_back(0);

        // 一个很容易遗漏的点就是：要想遍历到末尾加的这个数，还需呀更新n的值
        n += 1;

        // 前向扫描，求每个柱子的左边第一个比它小的柱子下标
        for (int i = 0; i < n; i++) {
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                // 此时，当前指针指向的值，小于栈顶指针。所以i是栈顶位置的元素的右边界
                // 那么，应该如何寻找栈顶元素的左边界呢？
                right = i;

                h = heights[st.top()];
                st.pop();
                // 我们发现，当经过一个出栈之后，当前栈顶，也就是第二个栈顶元素就是第一个栈顶元素的左边界。
                // 同时也是第三个栈顶元素（如果存在的话）的右边界
                left = st.empty() ? -1 : st.top();
                maxArea = max(maxArea, (right - left - 1) * h);
            }
            st.push(i);
        }
        return maxArea;
    }
};

int main(){
    Solution s;
    vector<int> test = {2,4};
    cout << s.largestRectangleArea(test) << endl;

    return 0;
}